package top.humbleyuan.double_pointer;

import top.humbleyuan.datastructure.linkedlist.LinkNode;

import java.util.HashSet;
import java.util.Set;

/**
 * @Author HumbleYuan
 * @Date 2020/5/18 22:14
 * @Des 环形链表,验证是否有环
 */
public class LeetCode_141 {

    public static void main(String[] args) {
        // 遍历哈希
        m1();

        // 双指针
        m2();
    }

    // 遍历哈希
    public static void m1() {
        /**
         * 数据准备
         */
        LinkNode head = new LinkNode(3);
        int[] vals = {2,0,-4};

        //末尾与第几个点结成环
        int ringIndex = 1;
        head = LinkNode.formLink(head,vals,ringIndex);


        LinkNode temp = head;
        Set<LinkNode> nodes = new HashSet<>();

        while(temp != null) {
            if(nodes.contains(temp)) {
                System.out.println("有环");
                return;
            }

            nodes.add(temp);
            temp = temp.next;
        }

        if(temp == null)
            System.out.println("无环");
    }


    // 快慢指针
    public static void m2() {
        /**
         * 数据准备
         */
        LinkNode head = new LinkNode(3);
        int[] vals = {2,0,-4,8,7,9,6};

        //末尾与第几个点结成环
        int ringIndex = 5;
        head = LinkNode.formLink(head,vals,ringIndex);

        LinkNode fast = head,slow = head;

        int step = 0;
        while (fast != null) {
            if(fast.next == null) {
                System.out.println("无环");
                return;
            }
            step ++;
            fast = fast.next.next;
            if (slow == fast) {
                System.out.println("有环,index:" + step);
                return;
            }
            slow = slow.next;

        }

        System.out.println("无环");
    }
}
